package com.monkeyboy.tree;

import com.monkeyboy.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 按照Z字类型打印二叉树
 * 解题思路：
 *  和按每一行打印的逻辑是差不多的，就是把每一层的先
 */
public class Tree09 {
    public ArrayList<ArrayList<Integer>> solution(TreeNode root) {
        if (root == null) {
            return null;
        }
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        boolean flag = false;
        while (!queue.isEmpty()) {
            ArrayList<Integer> preList = new ArrayList<>();
            int c = queue.size();
            while (c-- > 0) {
                TreeNode pre = queue.poll();
                if (pre == null) {
                    continue;
                }
                queue.add(pre.left);
                queue.add(pre.right);
                preList.add(pre.val);
            }
            flag = !flag;
            if (flag) {
                Collections.reverse(preList);
            }
            if (preList.size() != 0) {
                result.add(preList);
            }
        }
        return result;
    }
}
